#include <stdio.h>
#include <stdlib.h>

void Merge(int *A, int *L, int left, int *R, int right) {
    int i = 0, j = 0, k = 0;

    while (i < left && j < right) {
        if (L[i] < R[j])
            A[k++] = L[i++];
        else
            A[k++] = R[j++];
    }

    while (i < left) A[k++] = L[i++];
    while (j < right) A[k++] = R[j++];
}

void MergeSort(int *A, int n) {
    int mid, i, *L, *R;
    if(n < 2) return;

    mid = n / 2;

    L = (int*)malloc(mid * sizeof(int));
    R = (int*)malloc((n - mid) * sizeof(int));

    for (i = 0; i < mid; i++) L[i] = A[i];
    for (i = mid; i < n; i++) R[i - mid] = A[i];

    MergeSort(L, mid);
    MergeSort(R, n - mid);
    Merge(A, L, mid, R, n - mid);

    free(L);
    free(R);
}

int main() {
    const int numberOfElements = 7;
    int A[] = {5, 10, 45, 1, 0, 69, 7};

    MergeSort(A, numberOfElements);

    for (int i = 0; i < numberOfElements; i++)
        printf("%d ", A[i]);

    return 0;
}